
import javafx.util.Pair;

import java.util.*;

public class Solution3 {
    public List<String> topKFrequent(String[] words, int k) {
        // 1. 预处理原始字符数组-用哈希表，统计每个单词出现的频次
        HashMap<String, Integer> hash = new HashMap<>();
        for(String word : words) {
            hash.put(word,hash.getOrDefault(word,0) + 1);
        }
        // 2. 创建一个小根堆
        PriorityQueue<Pair<String,Integer>> heap = new PriorityQueue<>(
                (a,b) -> {
                    if(a.getValue().equals(b.getValue())) { // 频次相同时，字典序按照大根堆的方式排序
                        return b.getKey().compareTo(a.getKey());
                    }else { // 频次不同时，频次按照小根堆的方式返回
                        return a.getValue() - b.getValue();
                    }
                }
        );
        // 3. TopK 主逻辑
        for(Map.Entry<String,Integer> e : hash.entrySet()) {
            heap.offer(new Pair<>(e.getKey(),e.getValue()));
            if(heap.size() > k) {
                heap.poll();
            }
        }
        // 4. 提取结果
        List<String> ret = new ArrayList<>();
        while(!heap.isEmpty()) {
            ret.add(heap.poll().getKey());
        }
        // 逆序数组
        Collections.reverse(ret);
        return ret;
    }
}
